//翻转二叉树(力扣226)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp1=invertTree(root.left);
        TreeNode tmp2=invertTree(root.right);
        root.left=tmp2;
        root.right=tmp1;
        return root;
    }
}




//平衡二叉树(力扣110)
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getSize(root)!=-1;
    }
    public int getSize(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftSize=getSize(root.left);
        int rightSize=getSize(root.right);

        if(leftSize==-1||rightSize==-1||Math.abs(leftSize-rightSize)>1){
            return -1;
        }
        return Math.max(leftSize,rightSize)+1;
    }
}



//对称二叉树(力扣101)
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSameTree(root.left,root.right);

    }
    public boolean isSameTree(TreeNode p,TreeNode q){
        if((p==null&&q!=null)||(p!=null&&q==null)){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.right)&&isSameTree(p.right,q.left);

    }
}

//二叉树的层序遍历(力扣102)
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //结果
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        //利用队列来层序遍历
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        //直到遍历完
        while(!queue.isEmpty()){
            //一层作为List<Integer>
            List<Integer> temp=new ArrayList<>();
            //该层的长度
            int size=queue.size();
            //一层一个循环
            while(size!=0){
                TreeNode num=queue.poll();
                size--;
                temp.add(num.val);
                //给下一层的元素添加到队列里去
                if(num.left!=null){
                    queue.offer(num.left);
                }
                if(num.right!=null){
                    queue.offer(num.right);
                }
            }
            //添加每一层
            ret.add(temp);
        }
        return ret;
    }
}